﻿namespace LearnDSLinearSearch;

public class BinarySearch
{
    public int Search(int[] array, int key)
    {
        int n = array.Length;
        int left = 0;
        int right = n;
        while (left <= right)
        {
            int mid = (right - left) / 2 + left;
            if (array[mid] == key)
                return mid;
            else if (array[mid] < key)
                left = mid + 1;
            else if (array[mid] > key)
                right = mid - 1;
        }

        return -1;
    }

    public int Search(int[] array, int key, int left, int right)
    {
        if (left > right)
            return -1;
        else
        {
            int mid = (right - left) / 2 + left;
            if (key == array[mid])
                return mid;
            else if (key < array[mid])
                return Search(array, key, left, mid - 1);
            else if (key > array[mid])
                return Search(array, key, mid + 1, right);
        }

        return -1;
    }
}